package main.java.indi.zyj.coderecord;

public class LongestPalindrome {
    public String longestPalindrome(String s) {
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        boolean[][] dp = new boolean[len][len];
        int maxlenth = 0;
        int left = 0, right = 0;

        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (charArray[i] == charArray[j]) {
                    if (j - i < 2){
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                    }
                } else {
                    dp[i][j] = false;
                }
                if (dp[i][j] && j - i + 1 > maxlenth) {
                    maxlenth = j - i + 1;
                    left = i;
                    right = j;
                }
            }
        }
        return s.substring(left, left + maxlenth);
    }

    public static void main(String[] args) {
        new LongestPalindrome().longestPalindrome1("babad");
    }

    public String longestPalindrome1(String s) {

        if (s == null || s.length() == 0) return "";

        int left = 0, right = 0;
        int len = 1, maxLen = 0, maxLeft = 0;

        // 要先遍历左右再中心向两边扩展
        for (int i = 0; i < s.length(); i++) {
            left = i - 1;
            right = i + 1;
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                left--;
                len++;
            }
            while (right < s.length() && s.charAt(right) == s.charAt(i)) {
                right++;
                len++;
            }
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
                len += 2;
            }
            if (maxLen < len) {
                maxLeft = left;
                maxLen = len;
            }
            len = 1;
        }

        return s.substring(maxLeft + 1, maxLeft + maxLen + 1);
    }













}
